ass Solution {
public:
//235843009900348532
    bool is_pal(long long num,string& s)
    {
       // cout<<num;
        if(num==0)
        {
        s.push_back('0');
        return true;
        }
        while(num)
        {
            s.push_back(num%10+'0');
         //   cout<<num%10<<endl;
            num/=10;
        }
        auto it=s.begin();
        auto it1=s.end()-1;
        while(it<it1)
        {
            if(*it!=*it1)
            return false;
            it++;
            it1--;
        }
        return true;

    }
    long long strtoint(string& s)
    {
       // cout<<s.size()<<endl;
      // cout<<s<<endl;
        long long n=s.size()-1;
        long long i=0;
        long long res=0;
        while(n>=0)
        {
      
         //   cout<<(s[i]-48)*pow(10,n)<<endl;
            res+=(long long)((long long)(s[i]-48)*(long long)pow(10,n));
    
         //   cout<<res<<endl;
            n--;
            i++;
        }
     //   cout<<res;
        return (long long)res;
    }
    string nearestPalindromic(string n) {
        //10的幂
        int z=0;
        while(z<=18)
        {
        if(pow(10,z)==strtoint(n))
        {
            string res;
            is_pal(strtoint(n)-1,res);
            return res;
        }
        z++;
        }
        auto it=n.begin();
        int sin=1;
         if(strtoint(n)<=10)
        {
            string res;
            is_pal(strtoint(n)-1,res);
            return res;
        }
        while(it!=n.end())
        {
            if(*it!='9')
            {
            sin=0;
            break;
            }
            it++;
        }
        if(sin==1)
        {
            string res;
           is_pal(strtoint(n)+2,res);
            return res;
        }
        //本身就是回文数的情况
        string tmpp;
        if(is_pal(strtoint(n),tmpp))
        {
        string res;
        long long tmp=strtoint(n)-2;
      //  cout<<tmp<<endl;
        if(is_pal(tmp,res))
        return res;
        long long st=strtoint(n);
        int change1=n.size()/2;
        int change2=change1-1;
        if(n.size()%2==0)
        {
            if(n[change1]>'0')
            {
            n[change1]-=1;
            n[change2]-=1;
            
            return n;
         
            }
            else
            {
                n[change1]+=1;
                n[change2]+=1;
       
            return n;
         
            }
        }
        else
        {
            if(n[change1]>'0')
            n[change1]-=1;
            else
            n[change1]+=1;
         
            return n;
        
        }
        }

        string res1;
        string res2;
        res1=n;
        //cout<<res1;
        auto itl=res1.begin();
        auto itr=res1.end()-1;
        while(itl<itr)
            *itr--=*itl++;
      //  cout<<res1;
          //  cout<<res1;
        int ch1=res1.size()/2;
        int ch2=ch1-1;
        long long tmpw;
        if(res1<n)
        {
            if(res1.size()%2==0)
            {
               // cout<<res1;
            tmpw=(long long)strtoint(res1)+(long long)pow(10,ch1)+(long long)pow(10,ch2);
         
            // cout<<tmpw;
            }
            else 
            {
                tmpw=(long long)strtoint(res1)+(long long)pow(10,ch1);
             
            }
        }
        if(res1>n)
        {
            if(res1.size()%2==0)
            {
            tmpw=(long long)strtoint(res1)-(long long)pow(10,ch1)-(long long)pow(10,ch2);
               // cout<<tmpw<<endl;
         
           // cout<<res2;
            }
            else
            {
            tmpw=(long long)strtoint(res1)-(long long )pow(10,ch1);
           
            }     
        }
      //cout<<res2;
        if(is_pal(tmpw,res2))
        {
           if(abs(tmpw-strtoint(n))<abs(strtoint(res1)-strtoint(n)))
            return res2;
            else if(abs(tmpw-strtoint(n))==abs(strtoint(res1)-strtoint(n))&&tmpw<strtoint(res1))
            return res2;
       
            return res1;   
        }   
        else 
        return res1;
  
    }
};

class TopVotedCandidate {
private:
	vector<int> _persons;
	vector<int> _times;
	vector<int> _person_count;//存储候选人的票数
	int last_call_ans = -1;
	int last_max = 0;
	int half_serach(int t)
	{
		if (t >= _times[_times.size() - 1])
		{
			return _times.size() - 1;
		}

		int left = 0;
		int right = _times.size() - 1;
		while (left<right)
		{
			int mid = (left + right) >> 1;
			if (t >= _times[mid] && t<_times[mid + 1])
			{
				return mid;
			}
			if (t>_times[mid])
			{
				left++;
			}
			if (t<_times[mid])
				right--;
		}
		return -1;
	}
	//计算每个候选人的选票并选出最多的一个
	int Incremental_votes(int ans)
	{
		int tmp = last_call_ans;
		int max = 0;
		if (ans >= last_call_ans)
		{
			tmp++;
			while (tmp <= ans)
			{
				_person_count[_persons[tmp]]++;
				if (_person_count[_persons[tmp]] >= _person_count[max])
				{
					max = _persons[tmp];
					last_max = max;
				}
				tmp++;
			}
		}
		if (ans<last_call_ans)
		{
			while (tmp > ans)
//			{
//				_person_count[_persons[tmp]]--;
//				if (_person_count[_persons[tmp]] >= _person_count[max])
//				{
//					max = _persons[tmp];
//					last_max = max;
//				}
//				tmp--;
//			}
//		}
//		return max;
//	}
//public:
//	TopVotedCandidate(vector<int>& persons, vector<int>& times)
//		:_persons(persons)
//		, _times(times)
//	{
//		_person_count.resize(5000);
//	}
//
//	int q(int t) {
//		int ans = half_serach(t);
//		int res = Incremental_votes(ans);
//		last_call_ans = ans;
//
//
//		return res;
//	}
//};
